package OthersQuestions.q01_bitDanceInterview;

import java.util.Arrays;

/*
回溯
 */
public class Solution_2 {
    // 根据层深剪枝 & 排序后返回上一层剪枝
    public static void main(String[] args) {
        int[] nums = {1,2,7,3};
        Solution_2 demo = new Solution_2();
        System.out.println(demo.largestLessThanK(nums, 2147483647));
    }
    int k, num = 0, len, max = 0; // 假定给定的k为正数，无法组成比k小的数时返回0
    int[] nums;
    public int largestLessThanK(int[] nums, int k) {
        this.nums = nums;
        this.k = k;
        this.len = Integer.toString(k).length(); // 取得k的位数
        Arrays.sort(nums);
        backtrack(0);
        return max;
    }
    private void backtrack(int depth) {
        if(depth == len) return; // 剪枝：最大层深

        for(int i = 0; i < nums.length; i++) {
            num = num * 10 + nums[i];
            if(num > k) { // 剪枝：返回上层
                num = (num - nums[i]) / 10;
                return;
            }
            if(num > max) max = num;
            backtrack(depth + 1);
            num = (num - nums[i]) / 10; // 撤销
        }
    }


}
